Corelab Seminar
2018-2019
Theofilos Triommatis
Studying Permanent, #P complete problems and approximate algorithms for them
Abstract.
Permanent is a function very similar to determinant but despite their similarity, the former satisfies much fewer properties than the latter. In particular, there are efficient algorithms to compute determinant, however, there does not appear any way of computing permanent efficiently. Moreover permanent appears repeatedly in combinatorial problems as well as in statistical physics problems. In this thesis we shall present the algebraic properties that permanent satisfies and some basic theorems that mathematicians proved. Also we will see “how difficult” is to compute the permanent of a matrix, via classic complexity theory as well as algebraic complexity theory which was introduced by L. G. Valliant. Afterwards we will refer to some approximation algorithms for the permanent and we will study some other problems that seem to be equally difficult. By studying these problems we attempt to create an approximate deterministic algorithm for the permanent. And finally we will define formally some counting problems and we will construct a FPTAS to approximate their solutions.